/**
 * 给定二维数组，从左上到右下,每进入一格就加上当前格的值
 * 整个过程中必须始终保持累加和为正，问初始最小持有值是多少
 * 实际上就是问所有路径中，所有前缀和中的最小值的最大是多少。
 * 但是所有前缀和的最小值显然跟前缀和有关，而前缀和显然跟具体路径相关
 * 因此在某一点上，无法判断哪条路径往后走一定能够产生最小的前缀和。
 * 举个例子，如下
 * 1  -3  3
 * 0  -2  0
 * -3 -3 -3
 * 当到达(1, 2)这个点时，如果先从第一行走再向下走，则曾经出现过的最小值是-2
 * 如果先向下再右，则曾经出现过的最小值是-1，显然此时应该选第2条路径
 * 但是结合(2, 2)这个点就会发现第一条路径仍然是-2，而第二条路径则变为了-4。
 * 显然是因为两条路就的前缀和不同造成的，实际上如果(2, 2)是正数，则第2条路径优，
 * 如果是某些负数则第1条路径优。总之是有后效的，DP不成立。
 * 
 * 此情况下，如果设Dij是从起点到达(i,j)的最小值是不正确的。
 * 因此考虑设Dij是(i,j)到达终点所需要持有的最小值，这正是题目所问的
 * 如果向右走，则所需的最小值只需要 d + Aij >= D[i][j + 1] 即可
 * 因此 d = D[i][j + 1] - Aij
 * 向下走同理， 因此 D[i][j] = min(D[i][j + 1], D[i + 1][j]) - Aij
 * 如果所需的最小值是负数，说明走这条路径还有盈余，但是根据题目意思，直接定为1即可
 */
using llt = long long;
llt const MOD = 1E9 + 7;
llt const None = 0x7F2F3F4F;

class Solution {

using vll = vector<llt>;

int N, M;
vector<vll> D;
vector<vector<int>> *pVec;

public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        pVec = &dungeon;
        N = dungeon.size();
        M = dungeon[0].size();
        D.assign(N, vll(M, None));
        D[N - 1][M - 1] = dungeon[N - 1][M - 1] <= 0 ? 1 - dungeon[N - 1][M - 1] : 1;
        auto ans = dfs(0, 0);
        return ans;
    }


    llt dfs(int row, int col){
        if(None != D[row][col]) return D[row][col];
        
        auto value = (*pVec)[row][col];
        auto & d = D[row][col];
        if(row + 1 < N){
            chkUpdate(d, dfs(row + 1, col) - value);
        }
        if(col + 1 < M){
            chkUpdate(d, dfs(row, col + 1) - value);
        }
        d = max(d, 1LL);
        return d;
    }

    void chkUpdate(llt & d, llt a){
        if(None == a) return;
        if(None == d or d > a) return (void)(d = a);
        return;
    }

};

